package algorithms;

public class 合并已排序数组 {
    public static void main(String[] args) {
        int[][] arrOfArr = new int[][]{{1, 3}, {4, 5}, {0, 6, 9}, {2, 7, 8}};

        int[] arrValue = new int[]{};
        for (int i = 0; i < arrOfArr.length; i++) {
            arrValue = merge(arrValue, arrOfArr[i]);
        }

        printArr(arrValue);
    }

    private static void printArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    private static int[] merge(int[] a, int[] b) {
        int leftSize = a.length;
        int rightSize = b.length;

        int[] newArr = new int[leftSize + rightSize];

        int leftIndex = 0;
        int rightIndex = 0;
        int newArrIndex = 0;
        while (leftIndex < a.length && rightIndex < b.length) {
            if (a[leftIndex] <= b[rightIndex]) {
                newArr[newArrIndex] = a[leftIndex];
                leftIndex++;
                newArrIndex++;
            } else {
                newArr[newArrIndex] = b[rightIndex];
                rightIndex++;
                newArrIndex++;
            }

        }

        //copy remaining elements
        if (leftIndex >= a.length) {
            for (int i = rightIndex; i < b.length; i++) {
                newArr[newArrIndex] = b[i];
                rightIndex++;
                newArrIndex++;
            }
        }

        if (rightIndex >= b.length) {
            for (int i = leftIndex; i < a.length; i++) {
                newArr[newArrIndex] = a[i];
                leftIndex++;
                newArrIndex++;
            }
        }

        return newArr;
    }
}
